package leetcode100;

/**
 * @author shkstart
 * 描述
 * 在地下室里放着n种颜色的手套，手套分左右手，
 * 但是每种颜色的左右手手套个数不一定相同。
 * A先生现在要出门，所以他要去地下室选手套。
 * 但是昏暗的灯光让他无法分辨手套的颜色，只能分辨出左右手。
 * 所以他会多拿一些手套，然后选出一双颜色相同的左右手手套。
 * 现在的问题是，
 * 他至少要拿多少只手套(左手加右手)，才能保证一定能选出一双颜色相同的手套。
 * 给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,
 * 分别代表每种颜色左右手手套的数量。
 * 数据保证左右的手套总数均不超过26，且一定存在至少一种合法方案。
 * @create 2022-12-09-22:08
 */
public class Meme15_2 {
    public int findMinimum(int n, int[] left, int[] right) {
        // write code here

        //只需要找到左右手中最小的总和
        //用总和-最小的颜色+1
        int minLeft = Integer.MAX_VALUE;
        int minRight = Integer.MAX_VALUE;
        int sumLeft = 0;
        int sumRight = 0;

        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (left[i] * right[i] == 0) {
                //说明此时i这个颜色 只有单只
                //特殊情况，无法配对，只能全部拿走
                sum += left[i] + right[i];

            } else {
                minLeft = minLeft > left[i] ? left[i] : minLeft;
                minRight = minRight > right[i] ? right[i] : minRight;
                //这里的sum不能有单只，都是成双成对的才行
                sumLeft += left[i];
                sumRight += right[i];
            }
        }
        int result = 1 + sum + Math.min(sumLeft - minLeft + 1, sumRight - minRight + 1);
        return result;
    }
}
